import { findMinAndMaxValue, MinAndMaxParam } from '../search/min-max-search';

/**
 * 基数排序：一种特殊的桶排序，主要是对整数或字符串的每一位进行排序，可以从低位
 * 开始也可以从高位开始；桶的数量就是一个数的进制数或者叫基数。例如数组是十进制
 * 整数的，那么基数（桶数）就是10，分别是从0到9这样的10个桶；然后依次从个位、十位、
 * 百位、千位这样从低到高进行每一轮排序，结束后每位上都是相对有序的，整体上也是有序的。
 * @param array 目标数组
 * @param radixBase 基数（十进制就是10），也就是桶的个数
 * 如果数组里的元素是位数比较多的整数，那么就适合从高位开始排，位数比较低的就适合从低
 * 位开始排；时间空间复杂度都是O(n*k)，k是元素的位数。
 */
export function radixSort(array: number[], radixBase: number = 10) {
    // 长度不足2无需排序
    if (array.length < 2) {
        return array;
    }
    // 数组的最大值和最小值
    const { minValue, maxValue } = findMinAndMaxValue(array) as MinAndMaxParam<number>;
    // 当前处理的是个？十？百？千？万.....?
    let significantDigit: number = 1;
    // 从个位开始，一直处理到最高位
    while ((maxValue - minValue) / significantDigit >= 1) {
        // 构造桶数据
        const buckets: number[][] = createBuckets(array, radixBase, significantDigit, minValue);
        // 将桶里的数据一一取出放入临时数组
        const newArray = [];
        for (let i = 0, bl = buckets.length; i < bl; i ++) {
            if (buckets[i] != null) {
                newArray.push(...buckets[i]);
            }
        }
        // 将临时数组赋给目标数组，准备进行新一轮的处理
        array = newArray;
        // 处理位数升级，比如这次处理的是个位，下一轮就要处理十位了
        significantDigit *= radixBase;
    }
    return array;
}
/**
 * 生成桶数据，跟“桶排序”中的方法很像，只是我们多了一个参数，也就是当前处理位数
 * 比如基数是10，也就是10机制，那么第一次调这个函数是要处理的是个位，那第二次是十位，
 * 第三次就是百位......
 * @param array 目标数组
 * @param bucketSize 桶的大小
 * @param significantDigit 当前处理的位数
 * @param minValue 目标数组的最小值
 */
function createBuckets(
    array: number[],
    bucketSize: number,
    significantDigit: number,
    minValue: number,
): number[][] {
    // 构造桶这个二维数组
    const buckets: number[][] = new Array();

    // 遍历目标数组，将元素放入对应的桶中，桶满了就放入下一个桶中
    for (let i = 0, al = array.length; i < al; i ++) {
        // 目标数组遍历到的当前元素
        const current = array[i];
        // 当前元素会分布到哪个桶里（类似于计数排序）；分到桶后，桶之间是有大小顺序的。
        // 例如：当前值是679，最小值是1，当前处理的是十位。(679-1)/10=67.8，再对10取余并向下取整，是7
        const bucketsIndex = Math.floor((current - minValue) / significantDigit % bucketSize);
        // 没初始化就要初始化
        if (buckets[bucketsIndex] == null) {
            buckets[bucketsIndex] = [];
        }
        buckets[bucketsIndex].push(current);
    }
    // 返回桶这个数据，桶之间排序了，但桶内部还没有排序
    return buckets;
}
